<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>Document</title>
</head>
<body>

  <script>
    /*
      快速排序(递归二分法)
    */

    // 代码实现

    function quickSort(arr) {
      // arr 就是要排序的数组

      // 1. 先写停
      if (arr.length <= 1) return arr

      // 2. 按照递进书写
      // 2-1. 从 arr 的中间拿出一个数字来, 截取(splice)
      var centerIndex = parseInt(arr.length / 2)
      // 注意: splice 截取出来的返回值是一个数组, 数组中的 [0] 这一项才是中间那个数字呢
      var center = arr.splice(centerIndex, 1)[0]

      // 2-2. 准备两个新数组, 一个专门存放小的, 一个专门存放大的
      var small = []
      var big = []

      // 2-3. 遍历 arr 数组, 把小的放在小数组, 大的放在大数组
      for (var i = 0; i < arr.length; i++) {
        // 开始和 center 进行比较, 选择插入到 small 或者 big 中
        arr[i] < center ? small.push(arr[i]) : big.push(arr[i])
      }

      // 2-4. 把 小数组 中间值 大数组 合并成为一个完整数组
      //      出现递进关系, 小数组 和 大数组都需要地递进
      return [ ...quickSort(small), center, ...quickSort(big) ]
    }

    var res = quickSort([ 9, 4, 7, 3, 5, 6, 2, 8, 1 ])
    console.log(res)
  </script>
</body>
</html>
